
import java.util.ArrayList;
import java.util.List;
import java.util.Vector;


public class LionAlgorithm
{
	
	public static int largestAmbiguityGroupSize = -1;
	
	/**
	 * follows Lion algorithm from the article
	 * @param A coverage matrix
	 * @param P monitored components
	 * @param C list of components
	 * @return
	 */
	public static CoverageMatrix Lion(CoverageMatrix A, Vector<Component> P, List<Component> C)
	{
		CoverageMatrix Atag;
		Vector<Component> CDoubleTag, Ptag; 
		Vector<Component> Ctag = getLargestAG(A.getArray(), C);		
		
		if((largestAmbiguityGroupSize = Ctag.size()) == 1 )
		{
			return A;
		}
		int size = Ctag.size();
		Component c, cTag = Ctag.elementAt(0);
		
		for( int i=0; i< Ctag.size(); i++)
		{
			c = Ctag.elementAt(i);
			if(! P.contains(c) )
			{
				Atag = UpdateA(A, c);
				CDoubleTag = getLargestAG(Atag.getArray(), Ctag);
				if( CDoubleTag.size() < size)
				{
					size = CDoubleTag.size();
					cTag = c;
				}
			}
		}
		A = UpdateA(A, cTag);
		P.add(cTag);
		Ptag = P;
		return A;
	}
	
	/**
	 * 
	 * @param atag - an array represents the coverage matrix 
	 * @param Cs - 	the components who relevant in the calculation
	 * @return
	 */
	private static Vector<Component> getLargestAG(int[][] atag, List<Component> Cs)
	{
		Vector<Vector<Integer>>  AGs = LionAlgorithm.findAmbiguityGroups(atag, Cs);
		
		Vector<Integer> LAGs = new Vector<Integer>();
		int size = 0;
		for (int i = 0; i < AGs.size(); i++) 
		{
			if(AGs.elementAt(i).size() == size)
			{
				LAGs.add(i);
			}
			else if (AGs.elementAt(i).size() > size)
			{
				LAGs = new Vector<Integer>();
				LAGs.add(i);
				size = AGs.elementAt(i).size();
			}
		}
		
		Vector<Component> result = new Vector<Component>();
		if(LAGs.size() > 0)
		{
			Vector<Integer> LAG = AGs.elementAt(LAGs.elementAt(0));
			for (int i = 0; i < LAG.size(); i++)
			{
				result.add( getByID(Cs,LAG.elementAt(i)) );
			}
		}
		return result;
	}
	
	/**
	 * adding a line to the coverage matrix according to the component who is now monitored
	 * @param a	-  coverage matrix
	 * @param C - a new monitored component
	 * @return
	 */
	private static CoverageMatrix UpdateA(CoverageMatrix a, Component C)
	{		
		int [][] arr = a.getArray();
		CoverageMatrix result = new CoverageMatrix(arr, arr.length, arr[0].length);
		
		Vector<Integer> indexes = new Vector<Integer>();
		if(C != null)
		{
			Component curr = C;
			while(curr != null)
			{
				indexes.add(curr.getId());
				curr = curr.getPredecessor();
			}
			int[] newRow = new int[a.getArray()[0].length];
			for (int i = 0; i < indexes.size(); i++) 
			{
				newRow[indexes.elementAt(i)] = 1;
			}
			result.addRow(newRow);
			return result;
		}
		else
		{
			System.out.println("No component");
			return null;
		}
	}
	
	/**
	 * finds all ambiguity groups inside the coverage matrix
	 * @param CM - coverage matrix
	 * @param C	- components relevant
	 * @return
	 */
	private static Vector<Vector<Integer>> findAmbiguityGroups(int[][] CM, List<Component> C)
	{
		Vector<Vector<Integer>> result = new Vector<Vector<Integer>>();
		int[] Ci,Cj;
		
		boolean theChosenOnes[] = new boolean[CM[0].length]; 
		
		for(int i=0; i<CM[0].length; i++)
		{
			if(theChosenOnes[i] || !inC(i,C))
			{
				continue;
			}
			else
			{	
				Ci = getRow(CM, i);
				Vector<Integer> newAmbiguityGroup = new Vector<Integer>();
				newAmbiguityGroup.add(i);		
				theChosenOnes[i] = true;
				
				for(int j=i+1; j<CM[0].length; j++)
				{
					Cj = getRow(CM, j);
					if(identicalRows(Ci, Cj) && inC(j, C))
					{
						newAmbiguityGroup.add(j);
						theChosenOnes[j] = true;
					}					
				}
				result.add(newAmbiguityGroup);
			}
		}
		return result;
	}
	
	private static boolean inC(int i, List<Component> C)
	{
		boolean res = false;
		for (int j = 0; j < C.size() && !res; j++) 
		{
			if(C.get(j).getId() == i) res = true;
		}
		return res;
	}
	
	private static Component getByID(List<Component> C,int id)
	{
		for (int i = 0; i < C.size(); i++) 
		{
			if(C.get(i).getId() == id)
				return C.get(i);
		}
		return null;
	}
	
	private static int[] getRow(int[][] CM, int r)
	{
		int[] comp = new int[CM.length];
		for(int i=0; i<CM.length; i++)
			comp[i] = CM[i][r];
		return comp;
	}
	
	private static boolean identicalRows(int[] r1, int[] r2)
	{
		if(r1.length == r2.length)
		{
			boolean identical = true;
			for(int i=0; i<r1.length && identical; i++)
			{
				if(r1[i] != r2[i]) identical = false;
			}
			return identical;
		}
		else return false;
	}
	

}

